package br.unicamp.integralization.bab;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

import br.unicamp.integralization.dto.Allocation;
import br.unicamp.integralization.dto.History;
import br.unicamp.integralization.dto.Subject;
import br.unicamp.integralization.dto.SubjectGroup;

public class SolutionNode {
	// Qual foi a solução parcial que deu origem
	// a esta
	private SolutionNode parent;
	
	private List<Integer> electiveGroupCredits; 
	// O indice da disciplina que foi alocada
	private int subjectIndex;

	// Salva o indice do grupo no vetor de
	// groupElectives.
	// Se -2, representa uma disciplina extra-curricular
	private int subjectGroupIndex;

	private int upperBound, lowerBound, heuristicUpperBound;

	static private int[] restOfCredits;

	static boolean [][] subjectMatches;
	
	static int[] remainingGroupCredits;
	
	public SolutionNode() {
		parent = null;
		electiveGroupCredits = new ArrayList<Integer>();
		subjectIndex = -1;
		heuristicUpperBound=upperBound = lowerBound = Integer.MAX_VALUE;
	}

	//Retorna as matérias obrigatórias que foram removidas das matérias feitas pelo aluno.
	//Essas matérias serão utilizadas depois para montar o catálogo
	public List<Subject> initialize(History history) {
		List<Subject> mandatoryDone = new ArrayList<Subject>();
		
		//Removeremos as matérias obrigatorias
		//Elas serão obrigatoriamente colocadas no grupo das obrigatorias
		SubjectGroup mandatorySubjects = history.getAllocation().getMandatorySubjects();
		for (Iterator<Subject> it = mandatorySubjects.getSubjects().iterator(); it.hasNext();) {
			Subject mandatorySubject = it.next();	
			for (Iterator<Subject> jt = history.getSubjects().iterator(); jt.hasNext();) {
				Subject subject = jt.next();
				if(mandatorySubject.matches(subject)){
					mandatoryDone.add(subject);
					jt.remove();
				}
			} 
	
		}
		
		heuristicUpperBound=lowerBound = upperBound = 0;
		
		List<SubjectGroup> electiveGroups = history.getAllocation().getElectiveGroups();
		for (Subject subject : history.getSubjects()) {
			subject.updateMatchingGroups(electiveGroups);
		}
		
		Collections.sort(history.getSubjects());
		
		
		subjectMatches = new boolean [electiveGroups.size()][];

		//Monta a matriz de matches dizendo se a matéria i encaixa no grupo j
		for (int i = 0; i < electiveGroups.size(); i++) {
			SubjectGroup group = electiveGroups.get(i);
			upperBound +=  group.getCredits();
			electiveGroupCredits.add(Integer.valueOf( group.getCredits()));
			
			
			subjectMatches[i] = new boolean[history.getSubjects().size()];
			for (int j = 0; j < history.getSubjects().size(); j++) {
				subjectMatches[i][j]=false;
				for (int k = 0; k < group.getSubjects().size(); k++) {
					if(group.getSubjects().get(k).matches(history.getSubjects().get(j))){
						subjectMatches[i][j]=true;
						break;
					}
				}
			}
			
		}
		
		restOfCredits = new int[history.getSubjects().size()+1];
		remainingGroupCredits = new int[history.getSubjects().size()+1];
		
		int sum =0;
		for (int i = 0; i < history.getSubjects().size(); i++) {
			sum+=history.getSubjects().get(i).getCredits();
		}
		restOfCredits[0]=sum;
		for (int i = 1; i < restOfCredits.length-1; i++) {
			restOfCredits[i]=restOfCredits[i-1]-history.getSubjects().get(i).getCredits();
		}
		restOfCredits[restOfCredits.length-1]=0;
		
		
		
		return mandatoryDone;
	}

	public SolutionNode(SolutionNode parent) {
		this.parent = parent;
		this.subjectIndex = parent.subjectIndex + 1;
		this.electiveGroupCredits = new ArrayList<Integer>();
		for (Integer remainingCredit : parent.electiveGroupCredits) {
			this.electiveGroupCredits.add(remainingCredit.intValue());
		}
	}

	public List<SolutionNode> generateChilds(History history) {
		ArrayList<SolutionNode> childs = new ArrayList<SolutionNode>();
/*		Subject currentSubjectBeingAllocated = history.getSubjects().get(
				subjectIndex + 1);*/
		List<SubjectGroup> electiveGroups = history.getAllocation().getElectiveGroups();
		for (int i = 0; i < electiveGroups.size(); i++) {
			remainingGroupCredits[i]=electiveGroups.get(i).getCredits();
		}

		List<SubjectGroup> groups = history.getAllocation().getElectiveGroups();
		for (int i = 0; i < groups.size(); i++) {
			if(subjectMatches[i][subjectIndex+1] && remainingGroupCredits[i]>0){
					SolutionNode child = new SolutionNode(this);
					child.updateBoundsAndValue(history, i);
					childs.add(child);
			}
		}

		// Se nenhum filho foi criado, significa que a matéria não se encontrar
		// em nenhum
		// grupo, portanto é uma extra-curricular
		if (childs.size() == 0) {
			SolutionNode child = new SolutionNode(this);
			child.updateBoundsAndValue(history, -2);
			childs.add(child);
		}

		return childs;
	}

	private void updateBoundsAndValue(History history, int subjectGroupIndex) {
		if (subjectGroupIndex == -2) {// Temos uma extra-curricular aqui que não
										// se encaixa em nenhum lugar
			this.upperBound = parent.upperBound;
			this.lowerBound = parent.lowerBound;
			this.heuristicUpperBound = parent.heuristicUpperBound;
			this.subjectGroupIndex = subjectGroupIndex;
			return;
		}
		// subject = a matéria que estamos alocando no momento
		Subject subject = history.getSubjects().get(subjectIndex);

		// oldCredits = quantos créditos o grupo tinha antes de alocarmos
		// o subject no grupo group
		int oldCredits = electiveGroupCredits.get(subjectGroupIndex).intValue();

		// deltaCredits = quantos créditos foram reduzidos do grupo ao alocarmos
		// subject em grupo.
		// Note que pode ser que falte apenas 2 créditos mas esses 2 créditos
		// estão sendo matados com uma matéria de quatro créditos. Nesse caso
		// deltaCredits==2
		int deltaCredits = subject.getCredits();

		if (deltaCredits > oldCredits)
			deltaCredits = oldCredits;

		// Atualizamos os créditos restantes do group.
		electiveGroupCredits.set(subjectGroupIndex,oldCredits - deltaCredits);

		// No pior caso as matérias feitas(restantes) não se encaixam em nenhum
		// grupo.
		// Portanto só temos garantia de ter alocado as matérias que já foram
		// decididas.
		upperBound = parent.upperBound - deltaCredits;

		if(upperBound<0){
			System.out.println("Opa!");
		}
		// No melhor caso conseguimos fazer com que os créditos sejam todos
		// alocados em algum lugar
		lowerBound = Math.max(0, upperBound - sumRestOfCredits(subjectIndex+1));
		this.subjectGroupIndex = subjectGroupIndex;
		heuristicUpperBound= evalHeuristicUpperBound(this,history);
	}

	private int sumRestOfCredits(int i) {
		return restOfCredits[i];
	}

	public boolean isSolution(History history) {
		if(subjectIndex==40)
			System.out.println(history.getSubjects().size() + " " + subjectIndex);
		return history.getSubjects().size() == subjectIndex + 1;
	}

	public int getLowerBound() {
		return lowerBound;
	}

	public int getUpperBound() {
		return heuristicUpperBound;
	}

	// Retorna a melhor alocação de matérias
	public Allocation createAllocation(History clonedHistory,List<Subject> mandatorySubjects) {
		Allocation alloc = new Allocation();

		// Criamos subjectGroups vazios para irmos adicionando por índice
		// baseado na ordem em que aparecem no historico original
		// Adicionamos um grupo a mais onde ficaram as extra-curriculares
		for (int i = 0; i < clonedHistory.getAllocation().getElectiveGroups()
				.size() + 1; i++) {
			alloc.getElectiveGroups().add(new SubjectGroup());
		}
		
		for (Subject subject : mandatorySubjects) {
			alloc.getMandatorySubjects().addCatalogueSubject(subject);
		}
		

		SolutionNode current = this;
		while (current.subjectIndex != -1) {
			Subject subject = clonedHistory.getSubjects().get(
					current.subjectIndex);
			if (current.subjectGroupIndex == -2) {//é uma matéria extra-curricular
				alloc.getElectiveGroups()
						.get(alloc.getElectiveGroups().size() - 1)
						.addCatalogueSubject(subject);
			} else {//é uma eletiva
				alloc.getElectiveGroups().get(current.subjectGroupIndex)
						.addCatalogueSubject(subject);
			}
			current = current.parent;
		}
		
		

		return alloc;
	}

	//Necessita que o upperBound já esteja atualizado
	static int evalHeuristicUpperBound(SolutionNode node,History history){
		int hUpperBound=node.upperBound;
		List<SubjectGroup> electiveGroups = history.getAllocation().getElectiveGroups();
		for (int i = 0; i < electiveGroups.size(); i++) {
			remainingGroupCredits[i]=electiveGroups.get(i).getCredits();
		}
		
		for (int i = node.subjectIndex+1; i < history.getSubjects().size(); i++) {
			Subject subject = history.getSubjects().get(i);
			for (int j = 0; j < electiveGroups.size(); j++) {
				if(remainingGroupCredits[i]>0 && subjectMatches[i][j]){
					int delta = subject.getCredits();
					if(remainingGroupCredits[i]-delta<0)
						delta=remainingGroupCredits[i];
					remainingGroupCredits[i]-=delta;
					hUpperBound-=delta;
				}
			}
		}
		if(hUpperBound<node.upperBound)
			System.out.println(node.upperBound-hUpperBound);
		return hUpperBound;
	}
	
	public int getSubjectIndex() {
		return subjectIndex;
	}

	
}
